package com.atguigu.binaryTree;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class TheLowestAncestor {
    public static TreeNode findTheLowestAncestor(TreeNode root,TreeNode o1,TreeNode o2){
        Map<TreeNode,TreeNode> map=new HashMap<>();
        map.put(root,root);
        process(root,map);
        Set<TreeNode> set=new HashSet<>();
        TreeNode cur=o1;
        while(cur!=map.get(cur)){
            set.add(cur);
            cur=map.get(cur); //o1往上窜
        }
        set.add(root);
        //此时Set中已经存放了o1,及其o1往上的所有父节点
        cur=o2;
        while(cur!=map.get(cur)){
            if(set.contains(cur)){
                return cur;
            }
            cur=map.get(cur);
        }
        return null;
    }
    public static void process(TreeNode root,Map<TreeNode,TreeNode> map){
        if(root==null){
            return;
        }
        map.put(root.left,root);
        map.put(root.right,root);
        process(root.left,map);
        process(root.right,map);
    }

}
